
enum Color { RED, BLACK };  
template<typename K, typename V>
struct RBTNode {
    pair<K, V> key;
    Color color;
    RBTNode<K, V>* left;
    RBTNode<K, V>* right;
    RBTNode<K, V>* parent; 
     RBTNode(const pair<K, V>& kv) : key(kv), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};  

template<typename K, typename V>
class RedBlackTree {
private:
    RBTNode<K, V>* root;
    void leftRotate(RBTNode<K, V>*& node);
    void rightRotate(RBTNode<K, V>*& node);
    void insertFixup(RBTNode<K, V>*& node);
    void transplant(RBTNode<K, V>*& u, RBTNode<K, V>*& v);
    RBTNode<K, V>* minimum(RBTNode<K, V>* node);
    RBTNode<K, V>* maximum(RBTNode<K, V>* node);
    RBTNode<K, V>* successor(RBTNode<K, V>* node);
    RBTNode<K, V>* predecessor(RBTNode<K, V>* node);
    void inorder(RBTNode<K, V>* node);
    void preorder(RBTNode<K, V>* node);
    void postorder(RBTNode<K, V>* node);
public:
    RedBlackTree() : root(nullptr) {}
    void insert(const pair<K, V>& kv);
    void erase(const K& key);
    RBTNode<K, V>* search(const K& key);
    void inorder();
    void preorder();
    void postorder();
};